package microsfot.java;

public class MaxSumOfSubArray {
	/**
	 * 使用双重循环计算最大值
	 * @param a
	 * @return
	 */
	public int max(int a[]){
		int max=0;
		
		int c=0;
		
		if(a.length<=0){
			return 0;
		}
		if(a.length==1){
			return a[0];
		}
		
		if(a.length==2){
			return a[0]>a[1]?a[0]:a[1];
		}
		
		for(int i=1;i<a.length;i++){
			int j=i-1;
			while(j>=0){
				max+=a[j];
				
				if(max>c){
					c=max;
				}
				
				j--;
			}
		}
		
		return c;
	}
	
	public int max2(int a[]){
		int max=0;
		int sum=0;
		for(int i=0;i<a.length;i++){
			if(max<0){
				max=a[i];
			}else{
				max+=a[i];
			}
			
			if(sum<max){
				sum=max;
			}
		}
		return sum;
	}
	
	public static void main(String[] args) {
		int a[]={1, -2, 3, 10, -4, 7, 2, -5};
		int max=new MaxSumOfSubArray().max2(a);
		System.out.println(max);
	}
}
